import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * 227. 基本计算器 II
 * https://leetcode-cn.com/problems/basic-calculator-ii/
 */
public class Solutions_227 {
    public static void main(String[] args) {
        String str1 = "3+2*2";  // output: 7
        String str2 = " 3/2 ";  // output: 1
        String str3 = " 3+5 / 2 ";  // output: 5
        String str4 = "42";  // output: 42

        List<String> inputs = new ArrayList<>();
        inputs.add(str1);
        inputs.add(str2);
        inputs.add(str3);
        inputs.add(str4);

        for (String input : inputs) {
            int result = calculate(input);
            System.out.println(result);
        }
    }

    /**
     * 解题思路：栈
     * 运算符默认为 + 号
     * 循环字符串 s 时，遇到数字则计算数字（连续的数字通过 while 一次计算出来）
     * 计算后，再根据之前记录的运算符（即数字前的运算符）将数字入栈
     * 关键：
     * 1. 运算符为 + 号，直接入栈
     * 2. 运算符为 - 号，数字为 -num，再入栈
     * 3. 运算符为 * 号，需要与前一元素相乘，即取出栈顶元素，相乘后，将结果入栈
     * 4. 运算符为 / 号，需要与前一元素相除，即取出栈顶元素，相除后，将结果入栈
     */
    public static int calculate(String s) {
        LinkedList<Integer> stack = new LinkedList<>();
        char[] arr = s.toCharArray();
        int cur = 0;
        // 数字前的运算符
        char opt = '+';
        for (int i = 0; i < arr.length; i++) {
            if (Character.isDigit(arr[i])) {
                // 数字
                cur = cur * 10 + arr[i] - '0';
                // 处理并计算连续的数字
                while (i < arr.length - 1 && Character.isDigit(arr[i + 1])) {
                    cur = cur * 10 + arr[i + 1] - '0';
                    i ++;
                }
                // 根据 cur 数字前的运算符，将数字入栈
                if (opt == '+') {
                    stack.push(cur);
                } else if (opt == '-') {
                    stack.push(-cur);
                } else if (opt == '*') {
                    int n = stack.pop() * cur;
                    stack.push(n);
                } else if (opt == '/') {
                    int n = stack.pop() / cur;
                    stack.push(n);
                }
                // 重置为 0
                cur = 0;
            } else if (arr[i] == ' ') {
                // 空格
                continue;
            } else {
                // 运算符
                opt = arr[i];
            }
        }

        int res = 0;
        while (!stack.isEmpty()) {
            res += stack.pop();
        }
        return res;
    }
}
